#include <bits/stdc++.h>
using namespace std;

struct TreeNode
{
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL)
    {
    }
};
class Solution
{
  public:
    void dfs(TreeNode* root, vector<TreeNode*> &arr)
    {
        if (root == nullptr)
            return;
        dfs(root->left, arr);
        arr.emplace_back(root->left);
        dfs(root->right, arr);
    }
    TreeNode *Convert(TreeNode *pRootOfTree)
    {
        vector<TreeNode *> arr;
        if (pRootOfTree == nullptr)
        {
            return nullptr;
        }
        dfs(pRootOfTree, arr);
        for (int i = 1; i < arr.size() - 1; i++)
        {
            arr[i]->left = arr[i - 1];
            arr[i]->right = arr[i + 1];
        }
        arr[0]->left = nullptr;
        arr[arr.size() - 1]->right = nullptr;
        if (arr.size() > 1)
        {
            arr[0]->right = arr[1];
            arr[arr.size() - 1]->left = arr[arr.size() - 2];
        }
        return arr[0];
    }
};
